package com.itheima.algorithm.binarysearch;


public class BinarySearch {
    /**
     * 二分查找基础班
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 找到则返回索引，找不到返回-1
     */
    public static int binarySearch(int[] a, int target) {
        int i = 0;
        int j = a.length - 1;
        while (i <= j) { //范围内有值
//            int mid = (i + j) / 2;
            // 无符号右移1位
            int mid = (i+j)>>>1;
            if (a[mid] < target) { // 目标值在右边
                j = mid - 1;
            } else if (target < a[mid] ) { // 目标值在左边
                i = mid + 1;
            } else {
                return mid;
            }

        }
        return -1;
    }


    /**
     * 改动版
     * @param a
     * @param target
     * @return
     */
    public static int binarySearchAlternative(int[] a, int target) {
        int i = 0;
        int j = a.length;
        while (i < j) { //范围内有值
            // 无符号右移1位
            int mid = (i + j) >>> 1;
            if (a[mid] < target) { // 目标值在右边
                j = mid;
            } else if (target < a[mid]) { // 目标值在左边
                i = mid + 1;
            } else {
                return mid;
            }

        }
        return -1;
    }

    /**
     * 问题1： 为什么是i<=j,意味着区间内有未比较的元素,而不是i<j
     */

    /**
     * 问题2： (i+j)/2 有没有问题, 有可能j值超过整数最大值
     */









}
